In overview, as illustrated in FIG. 1, known encoding methods of encoding input data (D1) 10 in an encoder 20 to generate corresponding encoded output data (E2) 30 involve applying one or more transformations 40a, 40b to the input data (D1) 10 to generate corresponding encoded transformed data 50, wherein the encoded transformed data 50 has associated therewith coding table data 60 defining one or more coding tables defining the one or more transformations employed. The encoded transformed data 50 and the coding table data 60, namely in combination the encoded output data (E2) 30, are often communicated via a data carrier and/or a data communication network to one or more decoders 80 which are operable to decode the encoded output data (E2) 30 to generate corresponding decoded data (D3) 90. Optionally, the decoded data (D3) is a regenerated version of the data (D1), but not limited thereto, for example when transcoding occurs in the one or more decoders 80. It is often desirable that the encoded output data (E2) 30 is compressed relative to the input data (D1) 10. Moreover, it is also desirable that the encoded output data (E2) 30 is compressed in a substantially lossless manner, so that the decoded data (D3) 90 is as accurate as feasible when compared with the input data (D1) 10. Data compression achievable in the encoded output data (E2) 30 relative to the input data (D1) 10 is potentially inefficient when the coding table data 60 is significant in size relative to the encoded transformed data 50, namely the coding table data 60 corresponds to a significant data overhead. In certain known implementations of the encoder 20, the coding table data 60 includes information indicative of frequencies, probabilities or ranges of the coded “symbols” present in the encoded transformed data 50 that were as original symbols in the input data (D1) 10. The coding table data 60 is not limited thereto. Optionally, the coding table data 60 also contains information related to the used transformations and their parameters.
Some known implementations use context information to modify the probabilities included in the coding table data 60. Use of context information is a very efficient way of modifying the probabilities, but it is only efficient for a certain type of data, for example when coding values of pixels in an image, or values after an image transformation has been implemented.
A basic implementation of a range codec is described, for example, at the Wikipedia Range coding site [Range encoding—Wikipedia, the free encyclopedia (accessed Dec. 13, 2013), URL: http://en.wikipedia.org/wiki/Range_encoding]. This basic implementation uses at least one <EOM> (end-of-message) symbol. Arithmetic coding, URL: http://en.wikipedia.org/wiki/Arithmetic_coding is very similar to the Range coding, but it uses one floating point number [0, 1] and an <EOD> (end-of-data) symbol. Moreover, range coding is used widely in applications that require data compression such as video coding and image coding. It is very good at coding large data sets when the probabilities of different possible symbols are known. However, if the nature of the data to be coded is such that the probabilities of the symbols are not known beforehand at the one or more decoders 80, it is necessary to send the probabilities of the symbols together with the encoded data (E2) 30. Otherwise, the compression efficiency of the range coding suffers greatly.
The delivery of the frequency, probability or range values requires inclusion of additional data, namely “consumes data”, thus affecting the overall compression efficiency achievable in the encoder 20. Moreover, when more accurate symbol frequencies, probabilities or range values are sent, an improved range coding compression efficiency is achievable. However, sending very accurate frequencies, probabilities or range values requires more data size. In other words, there is a trade-off between sending accurate frequencies, probabilities or range values for the symbols and achieving a best possible compression efficiency in the encoded data (E2).
In contemporary situations, the amount of data transferred and stored in the world is increasing rapidly. As transmission bandwidth and data storage are limiting parameters, a need for efficient data compression methods is of great advantage. Thus, there arises a need for improved methods of compressing data which provide enhanced compression efficiencies obtainable from using range coding, for example in cases where a size of the data to be compressed is not very large. Hence, there arises a need for a method that allows range coding to be used in cases where the use of range coding and similar was not previously feasible and/or beneficial.
In an earlier published European patent document EP 0166607 A2 (King, Reginald Alfred), there is described a method wherein the compression of transmission of samples of (audio) data, in particular time encoded symbols (TES), is potentially improved by presenting bits in a non-linear fashion (variable length codes) instead of a linear representation (fixed-length codes). The method uses precursor codes, which are used for delivering a probability order of occurrences of elements from an encoder to a decoder. That is, the method does not actually transmit probabilities but only their order, for as long as elements arrive.
In an earlier patent document U.S. Pat. No. 6,650,996 B1 (Garmin Ltd.), there are described systems, devices and methods which employ a data structure, wherein there are utilized a first data field defining a decoding structure for decoding canonical Huffman encoded data, and a second data field defining a symbol table. Moreover, the symbol table is adapted to provide a symbol associated with a low-frequency index.